package com.example.sudoku;

import java.util.Arrays;
import java.util.List;

abstract class AbstractSudokuSolver{
    public int solutions;
    // size of the board
    protected int S = SaveBoard.return_size();
    // how long the side is
    protected int side = SaveBoard.return_side();
    public int[][] solutionBoard;
    protected abstract void runSolver(int[][] sudoku);

//    调用validate函数判断数独是否有解
    public boolean solve(int[][] sudoku){
        if(!validateSudoku(sudoku)){
            return false;
        }
        S = SaveBoard.return_size();
        side = (int)Math.sqrt(S);
        runSolver(sudoku);
        if (solutionBoard != null) {
            return true;
        }
        return false;
    }

//    生成解的字符串
    public boolean solve(String[] s){
        return solve(fromCharArr(s));
    }
       private static int[][] fromCharArr(String[] s){
        int S = s.length;
        int[][] out = new int[S][S];
        for(int i = 0; i < S; i++){
            for(int j = 0; j < S; j++){
                int num = s[i].charAt(j) - '1';
                if (num >= 1 && num <= S)
                    out[i][j] = num;
            }
        }
        return out;
    }

//    打印解的板子
    public static void printSolution(int[][] result){
        int N = result.length;
        for(int i = 0; i < N; i++){
            String ret = "";
            for(int j = 0; j < N; j++){
                ret += result[i][j] + " ";
            }
            System.out.println(ret);
        }
        System.out.println();
    }

//    判断板子的每行每列每格是否满足要求
    public static boolean validateSudoku(int[][] grid){
        if (grid.length != 9&&grid.length!=16)
            return false;
        for(int i = 0; i < grid.length; i++){
            if (grid[i].length != grid.length)
                return false;
            for(int j = 0; j < grid[i].length; j++){
                if (!(i >= 0 && i <= grid.length))
                    return false;
            }
        }

        int N = grid.length;

        boolean[] b = new boolean[N+1];

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if (grid[i][j] == 0)
                    continue;
                if (b[grid[i][j]])
                    return false;
                b[grid[i][j]] = true;
            }
            Arrays.fill(b, false);
        }

        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if (grid[j][i] == 0)
                    continue;
                if (b[grid[j][i]])
                    return false;
                b[grid[j][i]] = true;
            }
            Arrays.fill(b, false);
        }
        
        int side = (int)Math.sqrt(N);
        
        for(int i = 0; i < N; i += side){
            for(int j = 0; j < N; j += side){
                for(int d1 = 0; d1 < side; d1++){
                    for(int d2 = 0; d2 < side; d2++){
                        if (grid[i + d1][j + d2] == 0)
                            continue;
                        if (b[grid[i + d1][j + d2]])
                            return false;
                        b[grid[i + d1][j + d2]] = true;
                    }
                }
                Arrays.fill(b, false);
            }
        }
        return true;
    }

//    通过dancinglinks求出数独的一个解
    static class SudokuHandler implements SolutionHandler{
        int size = SaveBoard.return_size();
        public int[][] Solution(List<DancingLinks.DancingNode> answer){
            int[][] result = parseBoard(answer);
            return result;
        }

        private int[][] parseBoard(List<DancingLinks.DancingNode> answer){
            int[][] result = new int[size][size];
            for(DancingLinks.DancingNode n : answer){
                DancingLinks.DancingNode rcNode = n;
                int min = Integer.parseInt(rcNode.C.name);
                for(DancingLinks.DancingNode tmp = n.R; tmp != n; tmp = tmp.R){
                    int val = Integer.parseInt(tmp.C.name);
                    if (val < min){
                        min = val;
                        rcNode = tmp;
                    }
                }
                int ans1 = Integer.parseInt(rcNode.C.name);
                int ans2 = Integer.parseInt(rcNode.R.C.name);
                int r = ans1 / size;
                int c = ans1 % size;
                int num = (ans2 % size) + 1;
                result[r][c] = num;
            }
            return result;
        }



        public SudokuHandler(int boardSize){
            size = boardSize;
        }

    }
}
